package leetcode.editor.cn.q1xx

import leetcode.editor.cn.TreeNode
import java.util.*

class Q173_Medium_BSTIterator(root: TreeNode?) {
    private val stack: Deque<TreeNode> = LinkedList()
    private var cur = root

    fun next(): Int {
        while (cur != null) {
            stack.push(cur)
            cur = cur!!.left
        }
        cur = stack.pop()
        val ret = cur!!.`val`
        cur = cur!!.right
        return ret
    }

    fun hasNext(): Boolean {
        return cur!!.right != null || stack.isNotEmpty()
    }
}